package com.leetcode.problems397;


import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution1 {

    private Map<Integer,Integer> memo = new HashMap<>();

    public int integerReplacement(int n) {
        if(n == 1){
            return 0;
        }
        Integer cache = memo.get(n);
        if( cache != null){
            return cache;
        }
        if(n % 2 == 0){
            memo.put(n,integerReplacement(n / 2) + 1) ;
        }else {
            memo.put(n,Math.min(integerReplacement((n  / 2 + 1)), integerReplacement(n / 2)) + 2) ;
        }
        return memo.get(n);
    }
    public static void main(String[] args) {
        System.out.println(new Solution1().integerReplacement(6));
    }
}
